/**
 * 在程序中表示图
 */

/**
 * <p>
 * 顶点类对象表示一个顶点，可能会包含很多信息
 * </p>
 * <p>
 * 示例程序中仅存储一个字母，例如A用来识别顶点
 * </p>
 */
class Vertex {
	public char mLabel;

	public boolean mWasVisited;

	public Vertex(char lab) {
		mLabel = lab;
		mWasVisited = false;
	}
}

class StackX {
	private final int SIZE = 20;
	private int[] mSt;
	private int mTop;

	public StackX() {
		mSt = new int[SIZE];
		mTop = -1;
	}

	public void push(int v) {
		mSt[++mTop] = v;
	}

	public int pop() {
		return mSt[mTop--];
	}

	public int peek() {
		return mSt[mTop];
	}

	public boolean isEmpty() {
		return (mTop == -1);
	}
}

class Graph {
	private final int MAX_VERTS = 20;
	// 顶点对象放在数组中维护
	private Vertex[] mVertexList;
	private int[][] mAdjMat;
	// 当前顶点的个数
	private int mVertNum;

	private StackX mStackX;

	public Graph() {
		mVertNum = 0;
		mVertexList = new Vertex[MAX_VERTS];
		// adjacency matrix - 邻接矩阵
		mAdjMat = new int[MAX_VERTS][MAX_VERTS];
		for (int i = 0; i < MAX_VERTS; i++) {
			for (int j = 0; j < MAX_VERTS; j++) {
				mAdjMat[i][j] = 0;
			}
		}

		mStackX = new StackX();
	}

	/**
	 * 添加顶点
	 */
	public void addVertex(char lab) {
		mVertexList[mVertNum++] = new Vertex(lab);
	}

	/**
	 * 添加边，无向图
	 */
	public void addEdge(int start, int end) {
		mAdjMat[start][end] = 1;
		mAdjMat[end][start] = 1;
	}

	/**
	 * 显示顶点
	 * 
	 * @param v
	 */
	public void displayVertex(int v) {
		System.out.print(mVertexList[v].mLabel);
	}

	/**
	 * <p>
	 * 深度优先搜索的关键在于能够找到与某一个顶点邻接且没有访问过的顶点
	 * </p>
	 * <p>
	 * 如何做到呢？
	 * </p>
	 * <p>
	 * 邻接矩阵是关键，找到指定顶点所在的行，从第一列开始向后寻找值为1的列； 列号是相邻顶点的号码。
	 * 检查这个顶点是否被访问过，如果访问过，那么就访问下一个顶点。
	 * </p>
	 * 
	 * @param j
	 * @return
	 */
	public int getAdjUnvisitedVertex(int v) {
		for (int j = 0; j < mVertNum; j++) {
			if (mAdjMat[v][j] == 1 && !mVertexList[j].mWasVisited) {
				return j;
			}
		}
		return -1;
	}

	/**
	 * minimum spanning tree (depth first) <br/>
	 * 最小生成树
	 */
	public void mst() {
		mVertexList[0].mWasVisited = true;
		mStackX.push(0);

		while (!mStackX.isEmpty()) {
			int currentVertex = mStackX.peek();
			// get next unvisited neighbor
			int v = getAdjUnvisitedVertex(currentVertex);
			if (v == -1) {
				mStackX.pop();
			} else {
				mVertexList[v].mWasVisited = true;
				mStackX.push(v);

				displayVertex(currentVertex);
				displayVertex(v);
				System.out.print(" ");
			}
		}

		for (int j = 0; j < mVertNum; j++) {
			mVertexList[j].mWasVisited = false;
		}
	}
}

